package com.kexinxin.util.search;

import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import com.kexinxin.bean.Skill;
import com.kexinxin.service.impl.SearchDAOImpl;


public class TreeUtil {

	private TreeNode root = new TreeNode();

	public TreeUtil() {
		create();
	}

	public TreeNode create() {
		root.skillName = "root";
		List<Skill> skillList = SearchDAOImpl.getSkillList();
		Collections.sort(skillList, new Comparator<Skill>() {

			public int compare(Skill o1, Skill o2) {
				if (o1.getFatherId() < o2.getFatherId()) {
					return -1;
				} else if (o1.getFatherId() > o2.getFatherId()) {
					return 1;
				}
				return 0;
			}

		});

		for (int i = 0; i < skillList.size(); i++) {
			TreeNode node = new TreeNode();
			node.skillId = skillList.get(i).getSkillId();
			node.skillName = skillList.get(i).getSkillName();
			node.fatherSkillId = skillList.get(i).getFatherId();
			if (skillList.get(i).getFatherId() == 0) {
				node.fatherNode = root;
				root.childNode.add(node);
			} else {
				TreeNode fathNode = getTreeNodeById(node.fatherSkillId);
				fathNode.childNode.add(node);
				node.fatherNode = fathNode;
			}
		}

		return root;
	}

	public TreeNode getTreeNodeById(int id) {
		TreeNode node = new TreeNode();

		Queue<TreeNode> q = new LinkedList<TreeNode>();

		q.add(root);
		while (!q.isEmpty()) {
			TreeNode temNode = q.remove();
			if (temNode.skillId == id) {
				return temNode;
			} else {
				for (int i = 0; i < temNode.childNode.size(); i++) {
					q.add(temNode.childNode.get(i));
				}
			}
		}

		return node;
	}

	public void previewTree(TreeNode threeNote) {
		TreeNode node = threeNote;

		Queue<TreeNode> q = new LinkedList<TreeNode>();

		q.add(threeNote);

		while (!q.isEmpty()) {
			TreeNode temNode = q.remove();
			System.out.println(temNode.skillName);
			for (int i = 0; i < temNode.childNode.size(); i++) {
				q.add(temNode.childNode.get(i));
			}
		}
	}

	public List<TreeNode> getInTreeNodeList(String str) {
		List<TreeNode> nodeList = new LinkedList<TreeNode>();

		Queue<TreeNode> q = new LinkedList<TreeNode>();

		q.add(root);

		while (!q.isEmpty()) {
			TreeNode temNode = q.remove();

			// System.out.println(temNode.skillName);
			if (str.contains(temNode.skillName.toLowerCase())) {
				nodeList.add(temNode);
			}
			for (int i = 0; i < temNode.childNode.size(); i++) {
				q.add(temNode.childNode.get(i));
			}
		}
		return nodeList;
	}

	public boolean isLeaf(TreeNode node) {
		if (node.childNode.size() == 0) {
			return true;
		}
		return false;
	}

	public List<TreeNode> getLeafChilden(TreeNode node) {

		List<TreeNode> nodeList = new LinkedList<TreeNode>();

		Queue<TreeNode> q = new LinkedList<TreeNode>();

		q.add(node);
		int flag = 0;
		while (!q.isEmpty()) {
			TreeNode temNode = q.remove();
			if (isLeaf(temNode)) {
				if (flag == 1) {
					nodeList.add(temNode);
				}
			}
			for (int i = 0; i < temNode.childNode.size(); i++) {
				q.add(temNode.childNode.get(i));
			}
			flag = 1;
		}

		return nodeList;

	}

	public List<TreeNode> getChildrenList(TreeNode node) {
		List<TreeNode> result = new LinkedList<TreeNode>();
		Queue<TreeNode> q = new LinkedList<TreeNode>();
		// result.add(node);
		q.add(node);
		int flag = 0;
		while (!q.isEmpty()) {
			TreeNode temNode = q.remove();
			if (flag == 1) {
				result.add(temNode);
			}
			for (int i = 0; i < temNode.childNode.size(); i++) {
				q.add(temNode.childNode.get(i));
			}
			flag = 1;
		}
		return result;
	}

	public List<TreeNode> getLeafChildSearchList(List<TreeNode> nodeList) {
		List<TreeNode> searchList = new LinkedList<TreeNode>();
		for (int i = 0; i < nodeList.size(); i++) {
			List<TreeNode> childrenList = getChildrenList(nodeList.get(i));
			int flag = 0;
			for (int j = 0; j < nodeList.size(); j++) {
				if (childrenList.contains(nodeList.get(j))) {
					// System.out.println(nodeList.get(j).skillName);
					flag = 1;
				}
			}
			if (flag == 0) {
				if (isLeaf(nodeList.get(i))) {
					searchList.add(nodeList.get(i));
				} else {
					List<TreeNode> list = getLeafChilden(nodeList.get(i));
					for (int j = 0; j < list.size(); j++) {
						searchList.add(list.get(j));
					}
				}

			}
		}
		return searchList;
	}

	public List<TreeNode> getChildSearchList(List<TreeNode> nodeList) {
		List<TreeNode> searchList = new LinkedList<TreeNode>();
		for (int i = 0; i < nodeList.size(); i++) {
			List<TreeNode> childrenList = getChildrenList(nodeList.get(i));
			int flag = 0;
			for (int j = 0; j < nodeList.size(); j++) {
				if (childrenList.contains(nodeList.get(j))) {
					// System.out.println(nodeList.get(j).skillName);
					flag = 1;
				}
			}
			if (flag == 0) {
				List<TreeNode> list = getChildrenList(nodeList.get(i));
				searchList.add(nodeList.get(i));
				for (int j = 0; j < list.size(); j++) {
					if (!searchList.contains(list.get(j)))
						searchList.add(list.get(j));
				}

			}
		}
		return searchList;
	}
}